package com.javabasic.algorithm.leetcode;

import java.util.Arrays;

/**
 * @author xiongmin
 * @version 1.0
 * @since Created by work on 2021-07-11 17:19
 * 274. H-Index
 * 思路：
 *
 * 1、首先看到h个元素大于等于某个值，N-h个元素小于等于某个值，这显然是一个有序序列的特征，所以自然而然的想到先将数组排序；
 *
 * 2、将数组排序之后，对于给定的某个i，我们知道有citations.length - i篇论文的引用数 ≥ citations[i]，i篇
 *    论文的引用数 ≤ citations[i]；
 *
 * 3、不妨设h = citations.length - i，即至多有h篇论文分别引用了至少citation[i]次，其余citations.length - h篇
 *    论文的引用数不多于citation[i]次。
 *
 *    既然如此，只要citation[i] ≥ h，就满足题意。
 */
public class HIndex {

    /**
     * 排序，二分法
     * 由题目意思可得出：最终结果会在1-n之间，利用该条件二分，选择出h的最大值
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        int len = citations.length;
        int low = 0, high = len - 1;
        int result = 0;
        Arrays.sort(citations);
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (check(len,mid,citations)) {
                // 我们的需求是要找出最大的H值，会在数组的个数值之间
                result = len - mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }

    /**
     * 条件判断是否符合H指数的条件
     * @param len
     * @param mid
     * @param citations
     * @return
     */
    private boolean check(int len, int mid, int[] citations) {
        return (len - mid) <= citations[mid];
    }
}